package com.tgy.greedy;

import lombok.Data;
import lombok.Getter;
import lombok.Setter;

import java.util.*;

/**
 * @Author: tgy
 * @Date: 2020-11-04 17:48
 */
public class KnapsackQuestion {

    @Getter
    @Setter
    public static class LastKnapsack {

        private List<Goods> goods = new ArrayList<>();

        private int allValue;

        @Override
        public String toString() {

            StringBuilder sb = new StringBuilder();

            sb.append("value:").append(allValue)
                    .append("\n goods:");

            for (Goods good : goods) {

                sb.append("\n").append(good);
            }

            return sb.toString();
        }
    }

    public LastKnapsack packeGoods(Goods[] goods,int knapsackWeight, Comparator<Goods> comparator) {


        if (Objects.isNull(goods) || goods.length == 0) {

            return null;
        }

        LastKnapsack lastKnapsack = new LastKnapsack();

        Arrays.sort(goods,comparator);

        int value = 0;
        for (int i = 0; i < goods.length; i++) {

            if (knapsackWeight >= goods[i].getWeight()) {

                lastKnapsack.goods.add(goods[i]);
                value += goods[i].getValue();
                knapsackWeight -= goods[i].getWeight();

                if (knapsackWeight <= 0) {

                    break;
                }
            }
        }

        lastKnapsack.allValue = value;
        return lastKnapsack;
    }

}
